package array.prefixsum;

/**
 * 前缀积、后缀积
 */
public class ProductExceptSelf {

    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // 从左到右的前缀积，prefixSum[i] 表示 nums[0] ~ nums[i] 的积
        int[] prefix = new int[n];
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i];
        }

        // 从右到左的后缀积，suffix[i] 是 nums[i ... n - 1]的积
        int[] suffix = new int[n];
        suffix[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i];
        }

        // 结果数组
        int[] res = new int[n];
        res[0] = suffix[1];
        res[n - 1] = prefix[n - 2];
        for (int i = 1; i < n - 1; i++) {
            // 除了 nums[i] 自己的元素积就是nums[i]左侧和右侧所有元素之积
            res[i] = prefix[i - 1] * suffix[i + 1];
        }

        return res;
    }

}
